package leetcode.剑指offer.前40;

import leetcode.剑指offer.pojo.TreeNode;
import org.junit.Test;

import java.util.*;

/**
 * @author :songyaozhang
 * @date :Created 2021/7/22 9:33
 * @description :https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/
 */
public class 剑指_07_重建二叉树 {
    @Test
    public void test() {
        Solution solution = new Solution();
        TreeNode root = solution.buildTree(new int[]{3, 9, 20, 15, 7}, new int[]{9, 3, 15, 20, 7});
        //preOrder(root);
        List<Integer> list = preOrder_noRecursion(root);
        System.out.println(list);
        System.out.println(inOrder_noRecursion(root));
        System.out.println(postOrder_noRecursion(root));
    }


     public void preOrder(TreeNode node) {
        if (node == null) return;
         System.out.print(node.val + "\t");
         preOrder(node.left);
         preOrder(node.right);
     }

    /**
     * 1、将根节点入栈
     * 2、将根节点右孩子入栈
     * 3、将根节点左孩子入栈
     * @param root
     * @return
     */
     public List<Integer> preOrder_noRecursion(TreeNode root) {
        if (root == null) return null;
        Stack<TreeNode> stack = new Stack<>();
         ArrayList<Integer> list = new ArrayList<>();
         stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            list.add(node.val);
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }
        return list;
     }

    /**
     * 1、先将根节点入栈
     * 2、再将当前节点的所有左孩子入栈，直到左孩子为空
     * 3、访问栈顶元素，如果存在左孩子，重复步骤二
     * 4、重复2、3
     * @param root
     * @return
     */
     public List<Integer> inOrder_noRecursion(TreeNode root) {
        if (root == null) return null;
        ArrayList<Integer> list = new ArrayList<>();
         Stack<TreeNode> stack = new Stack<>();
         TreeNode tmp = root;
         while (tmp != null || !stack.isEmpty()) {
             if (tmp != null) {
                 stack.push(tmp);
                 tmp = tmp.left;
             } else {
                 tmp = stack.pop();
                 list.add(tmp.val);
                 tmp = tmp.right;
             }
         }
         return list;
     }

    /**
     * 1、根节点入栈
     * 2、再将当前节点的所有左孩子入栈，直到左孩子为空
     * 3、得到栈顶元素的值，先不访问，判断元素是否存在右孩子，如果存在并且没有访问，则将右孩子入栈，否则访问栈顶元素
     * @param root
     * @return
     */
    /*
            3
        9       20
            15      7
     */
     public List<Integer> postOrder_noRecursion(TreeNode root) {
        if (root == null) return null;
         ArrayList<Integer> list = new ArrayList<>();
         Stack<TreeNode> stack = new Stack<>();
         TreeNode tmp = root;
         TreeNode pre = null;
         while (tmp != null || !stack.isEmpty()) {
             while (tmp != null) {
                 stack.push(tmp);
                 tmp = tmp.left;
             }
             if (!stack.isEmpty()) {
                 tmp = stack.peek();
                 if (tmp.right == null || tmp.right == pre) {
                     tmp = stack.pop();
                     list.add(tmp.val);
                     pre = tmp;
                     tmp = null;
                 } else {
                     tmp = tmp.right;
                 }
             }
         }
         return list;
     }

    class Solution {

        Map<Integer, Integer> map;
        public TreeNode buildTree(int[] preorder, int[] inorder) {
            map = new HashMap<>();
            for (int i = 0; i < inorder.length; i++) {
                map.put(inorder[i], i);
            }
            return buildTree0(preorder, inorder, 0, preorder.length - 1, 0, inorder.length - 1);
        }

        private TreeNode buildTree0(int[] preorder, int[] inorder,
                                    int preorder_left, int preorder_right, int inorder_left, int inorder_right) {
            if (preorder_left > preorder_right) return null;
            int preorder_root = preorder_left;
            Integer inorder_root = map.get(preorder[preorder_root]);

            TreeNode root = new TreeNode(inorder[inorder_root]);

            int size_left = inorder_root - inorder_left;

            root.left = buildTree0(preorder, inorder, preorder_left + 1, preorder_left + size_left, inorder_left, inorder_root - 1);

            root.right = buildTree0(preorder, inorder, preorder_left + size_left + 1, preorder_right, inorder_root + 1, inorder_right);
            return root;
        }
    }


}
